\documentclass[a4paper,10pt]{article}  
\usepackage{graphicx}
\usepackage{latexsym}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{color}
\usepackage[english]{babel}
\usepackage[latin1]{inputenc}
\usepackage{fancyhdr}
\usepackage{anysize}
%\pagestyle{fancy}
\marginsize{2cm}{2cm}{1cm}{4cm}

\begin{document}

\title{UT3 Cheat Detection \\ DMTM0910 Project Report}   
\author{Giuseppe Chindemi 750906 - Riccardo Cattaneo 755279}             
\maketitle

%\clearpage


\section{Methodology}
The mining process has been splitted into three steps:
\begin{itemize}
\item \textbf{Domain analysis and Gameplay analysis}, to better understand the data and the characteristic patterns of the cheats.
\item \textbf{Data exploration}, exploiting also techniques of visualization in order to reduce the search space.
\item \textbf{Data classification and Performance evaluation}, using Naive Bayes classifiers and k-folding cross-validation. 
\end{itemize}
It should be noticed that a big part of this work is based on the idea that many cheating patterns can be unveiled only considering statistics and summaries of the specific match dynamics. For this reason the available datasets were mainly used to extract these informations.

\section{Domain analysis}
The gameplay of UT3 has been analyzed in order to identify the most common cheating patterns. It has been discovered that there are two main families of cheats, described in Table \ref{builtin} and \ref{external}:
\begin{description}
\item[Built-in cheats] invocable as function of the game. These allow for e.g. maximum life, god-mode, infinite ammos. These cheats are not allowed by default in multi-player mode.
\item[External tools] that basically interpose between the game server and the game client to modify the behavior of the client in order to give the cheater an advantage in terms of e.g. increased movement speed, improved aim, improved enemy radar. These are typically more difficult to identify because are not part of the original game.
\end{description}

It should be noticed that some behaviors considered cheating in other FPS games are instead allowed in UT3 due to peculiar features of this game, for example: exceeding the initial value of life is allowed exploiting power-ups; some shields completely absorb damage without affecting player's health points.

\section{Data exploration}
It has been noticed that the datasets \textsl{per se} were not suitable for the identification of cheats, other than the simpler ones. Due to this fact a number of transformations have been applied to the datasets.\\
For the majority of the known cheats, it has been hypothesized a set of characteristics patterns and than applied suitable techniques of data visualization in order to possibly discover those patterns into the datasets. For a few other known cheats, for which was not possible to identify a precise pattern, it has been defined the subset of attributes supposed to be correlated to the presence of the cheat and than applied a classifier in order to possibly recognize a characteristic pattern. Moreover, assuming possible the presence of unknown cheats in the datasets and supposing that they would appear in the same attribute spaces of the already known cheats, it has been applied a classifier to those spaces in order to identify unknown patterns. Afterwards this new patterns have been either associated to a known cheat or identified as characterizing of a new cheat or rejected as meaningless.\\

Built-in cheats have been considered first. Those cheats can be discovered in the raw datasets and their respective patterns have been mined by means of visualization techniques. Follows the list of the obtained results.

\noindent\textbf{GOD [Not Found]} CHP never decreases even though hit and armor-less. A TimeElapsed vs CHP chart has been plotted in order to discover this pattern, but it has never been found.

\noindent\textbf{FLY [Not Found]} CFlying attribute true for a long enough time. No player flew continuously for more than 1 sec, so it has been deduced the cheat was not active.

\noindent\textbf{LOADED [Not Assessable]} All weapons instantaneously loaded with full ammo. Lack of information in the data.

\noindent\textbf{ALLAMMO [Not Assessable]} Instantaneously all ammos. Lack of information in the data.
	
\noindent\textbf{ALLWEAPONS [Not Assessable]} Instantaneously all weapons. Lack of information in the data. 
 
\noindent\textbf{GHOST [Not Assessable]} Movement trough walls and flying. Lack of map information in the data.
 
\noindent\textbf{TELEPORT [Not Assessable]} Instantaneous transportation to the cross-hair's location. Lack of map information in the data (presence of teleport platforms).\\

After the analysis of the built-in cheats it has been analyzed the presence of external tools influences.

\noindent\textbf{VISIBILITY CHECK [Not Assessed]} Knowing the AimResult value of the opponent, how much the player is visible to the enemies and how much enemies are visible to the player, it has been supposed that the cheater would be more elusive than a non-cheater when aimed at. This hypotheses was not assessed due to the necessity of further refinement of both the suitable attribute search space and the pattern itself.

\noindent\textbf{AUTOAIM [Found]} The player aims too frequently too well when the enemy is visible. It has been discovered that when the cheat is active, the distribution of the points of the chart EnemyVisible vs CAimResult is higly biased towards very high values of CAimResults, with a very little variance of this process (see \figurename~\ref{fig:autoaim}).

\noindent\textbf{AUTOFIRE [Found]} Player fires almost each time that the enemy is aimed. It has been discovered that when the cheat is active, the number of "non fires"  with the enemy well aimed is considerably lower than when the cheat is not active (see \figurename~\ref{fig:autofire}). 

\noindent\textbf{RADAR [Not Assessed]} Shows the position of the enemies and of the power-ups on the mini-map. A possible pattern can involve the variation of enemy distance related to he HP. However further refinement of both the suitable attribute search space and the pattern itself were needed to validate this pattern.

\noindent\textbf{ENEMY INFO [Not Assessable]} The cheater knows forbidden information related to the opponents. It has not been hypothesized a suitable pattern.\\

Verified the influence of external tools, it has been evaluated the presence of unknown cheats in the datesets applying a classifier to both the raw original datasets and the features generated to discover the other cheats. The majority of the resulting patterns have been ascribed as side-effect of other cheats, while the remaining ones discarded because meaningless.  

\section{Data classification and Performance evaluation}
A specific classifier has been trained for each of the cheats discovered in the datasets. All these classifiers were then combined into one process in order to obtain a unique cheat detection system.
\begin{description}
\item[AUTOAIM Classifier]
A Naive Bayes classifier was trained on a transformed dataset containing one summary tuple for each one of the original datasets. Every tuple exports aggregate informations extracted from the corresponding dataset, considered meaningful for the specific task: mean, variance, median and mode of CAimResult values, considering only the tuples where EnemyVisible = True. \\
The classifier was validated using k-folding (k = 4) cross-validation and achieved an accuracy of 100\%.\\
In order to further improve the performance, it has been considered the possibility of training a player-specific classifier. However, due to the fact that the usage of the cheat significantly influence the aim results of both expert and novice players, this option has been discarded and the general classifier kept. 
\item[AUTOFIRE Classifier]
A Naive Bayes classifier was trained on a transformed dataset containing one summary tuple for each one of the original datasets. Every tuple exports aggregate informations extracted from the corresponding dataset, considered meaningful for the specific task. Only the tuples where EnemyVisible = True have been considered. The datasets have been repeatedly filtered for increasing CAimResult thresholds. After each filtering, the aggregate value count(CFiring = False) / [ count(CFiring = True) + count(CFiring = False) ] has been computed. \\
The classifier was validated using k-folding (k = 4) cross-validation and achieved an accuracy of 100\%.\\
\end{description}
It has been chosen to use Naive Bayes classifiers due to both the simplicity of these classifiers and the high dimensionality of some spaces used as training set.

\section{Conclusions}
In the tests, the final classification system correctly recognizes and distinguishes all the identified cheats, with an accuracy of 100\% when applied on the training data.\\

\section*{List of Tables and Figures}

\begin{table}[h!]
\centering
\begin{tabular}{p{0.2\textwidth} p{0.6\textwidth}}
\hline
Built-in		&	\\
\hline
Cheat Name	& Description		\\
\hline
GOD 	& God mode: infinite ammo and health, player is immune to damage \\
FLY	& Let player fly \\
LOADED & All weapons with full ammo \\
ALLAMMO & Gives player max ammo \\
ALLWEAPONS & Gives player all weapons \\
GHOST & Enables movement trough walls and flying \\
TELEPORT & Enables instantaneous transportation to the cross-hair's location\\
\hline
\end{tabular}
\caption{\label{builtin}Cheats available trough the built-in command line.}
\end{table}

\begin{table}[h!]
\centering
\begin{tabular}{p{0.2\textwidth} p{0.6\textwidth}}
\hline
External & \\
\hline
Cheat Name & Description \\
\hline
VISIBILITY CHECK & Let the player know the AimResult of the opponent, how much  the player is visible to the enemies and how much enemies are visible to the player\\
AUTOAIM & Let the player automatically aim enemies\\
AUTOFIRE & Player fires automatically when enemy is aimed\\
RADAR & Shows the position of the enemies and of the power-ups on the mini-map\\
ENEMY INFO & Shows informations regarding status of the aimed enemy\\
\hline
\end{tabular}
\caption{\label{external}Cheats available trough popular external tools.}
\end{table}

\begin{figure}[h!]
	\begin{center}$
		\begin{array}{cc}
			\includegraphics[width=0.49\textwidth]{img/EVvsCAR_RisingSun-Novice-Cheat-Pippero.png} &
			\includegraphics[width=0.49\textwidth]{img/EVvsCAR_RisingSun-Novice-NoCheat-Pippero.png}
		\end{array}$
	\end{center}
	\caption{\label{fig:autoaim} Same player, same map. On the left with AUTOAIM enabled and on the right with AUTOAIM disabled. X axis: EnemyVisible attribute [false, true]. Y axis: CAimResult attribute [-1000, +1000]}
\end{figure}

\begin{figure}[h!]
	\begin{center}$
		\begin{array}{cc}
			\includegraphics[width=0.49\textwidth]{img/EVvsCARvsCF_RisingSun-Novice-Cheat-Pippero.png} &
			\includegraphics[width=0.49\textwidth]{img/EVvsCARvsCF_RisingSun-Novice-NoCheat-Pippero.png}
		\end{array}$
	\end{center}
	\caption{\label{fig:autofire} Same player, same map. On the left with AUTOFIRE enabled and on the right with AUTOFIRE disabled. X axis: EnemyVisible attribute [false, true]. Y axis: CAimResult attribute [-1000, +1000]. Color: CFiring [blue, red]}
\end{figure}

\end{document}
